#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
# http://www.careercup.com/question?id=14813758
"""
Given 2 arrays A,B, where x(A.length) < y(B.length), we want to
insert (y - x) 0's to A at various places such that A*B is minimum. For instance, if A = (1, -1) and
B = (1,2, 3, 4), then inserting two 0's in the middle of A such that A = (1, 0, 0, -1) would minimize
A*B. I think he was looking for a dynamic problem solution.
"""
import os, re, sys, getopt
import logging
import locale

def min_multi_helper(A, B, i, j, matrix, positions):
    if (i, j) in matrix: return matrix[(i, j)]
    result = 0
    if i == j - 1:
        result, positions[(i, j)] = 0, 0
    elif j == 0:
        result = B[i] * A[i]
        if i != 0: result += min_multi_helper(A, B, i - 1, 0, matrix, positions)
        positions[(i, j)] = A[i]
    else:
        fill_0, fill_non_0 = min_multi_helper(A, B, i - 1, j - 1, matrix, positions), B[i] * A[i - j] + min_multi_helper(A, B, i - 1, j, matrix, positions)
        if fill_0 < fill_non_0: result, positions[(i, j)] = fill_0, 0
        else: result, positions[(i, j)] = fill_non_0, A[i - j]
    matrix[(i, j)] = result
    return result

def min_multi_david(A, B):
    matrix, positions = {}, {}
    result = min_multi_helper(A, B, len(B) - 1, len(B) - len(A), matrix, positions)
    #print positions
    return result

def min_multi_lobatt(a, b):
    if len(a) < len(b): return 0, []
    zeros = len(a) - len(b)
    m = []
    for i in range(0, (len(b)+1)):
       m.append([0] * (zeros + 1))
    import copy
    r = copy.deepcopy(m)
    m[0][0] = 0 
    for i in range(1, len(b) + 1):
        m[i][0] = m[i - 1][0] + a[i - 1] * b[i - 1]
    for i in range(1, len(b) + 1):
        for j in range(1, zeros + 1):
            r[i][j] = m[i][j - 1] < a[i + j - 1] * b[i - 1] + m[i -1][j] and r[i][j - 1] + 1 or 0
            m[i][j] = min(m[i][j - 1], a[i + j - 1] * b[i -1] + m[i -1][j])

    #print_matrix(r)
    #print_matrix(m)

    i = len(b)
    j = zeros
    result = []
    while i > 0:
        if r[i][j] > 0: 
            result.extend([0] * r[i][j])
            j -= r[i][j]
        else:
            result.append(b[i - 1])
            i -= 1

    result.extend([0] * (len(a) - len(result)))
    return m[len(b)][zeros], result[::-1]

if __name__ == '__main__':
    from utils import *
    for i in range(0, 10):
        A = random_arr(4, -2, 5)
        B = random_arr(8, -1, 6)
        david = min_multi_david(A, B)
        lobatt, dummy  = min_multi_lobatt(B, A)
        if david != lobatt:
            print A
            print B
            print david
            print lobatt
        else:
            print A
            print B
            print "PASS"
        print ""
